#define _CRT_SECURE_NO_WARNINGS
#include <iostream>
#include <vector>
using namespace std;

void quickSort(vector<int>& arr, int begin, int end)
{
	if (begin >= end)  return;
	int key = arr[begin + rand() % (end - begin + 1)];
	int cur = begin, left = begin - 1, right = end + 1;
	while (cur != right)
	{
		if (arr[cur] < key)  swap(arr[++left], arr[cur++]);
		else if (arr[cur] == key)  cur++;
		else  swap(arr[--right], arr[cur]);
	}
	quickSort(arr, begin, left);
	quickSort(arr, right, end);
}
int main()
{
	srand(time(nullptr));
	vector<int> arr = { 10, 9, 8, 7, 6, 5, 4, 3, 2, 1, 0 };
	quickSort(arr, 0, arr.size() - 1);
	for (auto& e : arr)  cout << e << " ";
	cout << endl;
	return 0;
}